//: [Previous](@previous)

/*:
 # 基数排序
 * 最好情况 O(n*k))
 * 最坏情况 O(n*k))
 * 平均时间复杂度 O(n*k))
 * 空间复杂度 O(n+k)
 
 基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。
 
 基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。
 
 1. 将个位数按0...9分别入桶
 2. 取出各桶位得到个位数排序
 3. 将十位数按0...9分别入桶
 4. 取出各桶位得到十位数排序
 5. ...
 
 */

import Foundation

var numbers = [121,3, 38, 6, 27, 5, 2, 272, 7, 67, 9, 1, 395, 4, 3,11]
print("排序前 \(numbers)")

func redixSort(_ arr: [Int]) -> [Int] {
    
    var maxLength = 0
    var max = arr[0]
    for i in 0..<arr.count {
        if max < arr[i] {
            max = arr[i]
        }
    }
    
    while max > 0 {
        maxLength += 1
        max = max / 10
    }
    
    return sort(arr, maxDigit: maxLength)
}

func sort(_ arr: [Int], maxDigit: Int) -> [Int] {
    
    var divisor = 1
    var digit = 1
    var nums = arr
    
    while digit <= maxDigit {
        // 创建桶
        var buckers: [[Int]] = Array(repeating: [], count: 10)
        
        // 入桶
        for i in 0..<nums.count {
            let index = (nums[i] / divisor) % 10
            buckers[index].append(nums[i])
        }
        // 出桶
        var temp: [Int] = []
        for bucker in buckers {
            temp += bucker
        }
        nums = temp
        digit += 1
        divisor *= 10
    }
    return nums
}

print("排序后 \(redixSort(numbers))")

//: [Next](@next)
